package offer;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * <p>
 * 剑指 Offer 41. 数据流中的中位数
 * </p>
 *
 * @author xiaozuolin
 * @date 2021/9/24 16:20
 */
public class MedianFinder {
    Queue<Integer> A;
    Queue<Integer> B;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        A = new PriorityQueue<>();//小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x));//大顶堆，保存较小的一半
    }

    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}
